We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings, including aspect ratio, vertex resolution, edge length, edge separation, and edge curvature, as well as complexity measures such as vertex and edge representational complexity and the area of the drawing. In addition to this general framework, we present algorithms that operate within this framework. Specifically, we describe an algorithm for drawing any n-vertex planar graph in an O(n) \times O(n) grid using polylines that have at most two bends per edge and asymptotically-optimal worst-case angular resolution.More significantly, we show how to adapt this algorithm to draw any n-vertex planar graph using cubic Bézier curves, with all vertices and control points placed within an O(n) \times O(n) integer grid so that the curved edges achieve a curvilinear analogue of good angular resolution. All of our algorithms run in O(n) time.
展开▼
机译:我们描述了用于绘制具有折线和曲线的平面图的美学标准和复杂性度量的统一框架。该框架包括此类图形的几个视觉属性,包括纵横比,顶点分辨率,边缘长度,边缘分离和边缘曲率,以及复杂性度量,例如顶点和边缘表示的复杂性以及图形的面积。除了这个通用框架,我们还介绍了在该框架内运行的算法。具体来说,我们描述了一种使用折线在O(n)\ times O(n)网格中绘制任何n顶点平面图的算法,该折线的每个边缘最多具有两个折弯并且渐近最优的最坏情况下的角分辨率。我们展示了如何使用该算法使用三次Bézier曲线绘制任何n顶点平面图,并将所有顶点和控制点放置在O(n)\ times O(n)整数网格内,从而使曲线边缘实现曲线模拟具有良好的角度分辨率。我们所有的算法都在O(n)时间内运行。
展开▼